//
// Description: 01背包问题 模板
// Created by Loading on 2021/8/8.
//

// 例题：01背包问题，https://www.acwing.com/problem/content/description/2/

#include <bits/stdc++.h>

using namespace std;

// 参数：
// goods[i][0] 为第 i 个物品的体积，goods[i][1] 为第 i 个物品的价值
// V 为背包最大容量

/* 空间优化版动态规划，O(NV) */
int solve_0_1_backpack_Space_optimization(vector<vector<int>> &goods, int V) {
    // 体积
    int v[goods.size() + 1];
    // 价值
    int w[goods.size() + 1];
    for (int i = 0; i < goods.size(); ++i) {
        v[i + 1] = goods[i][0];
        w[i + 1] = goods[i][1];
    }

    // 动态规划数组，dp[i] 表示体积 <= i 时的最大价值
    /* 由于二维 dp 数组更新时只用到了上一层的数据，所以可以压缩成一维数组 */
    int dp[V + 1];
    for (int i = 1; i <= goods.size(); ++i) {
        /* 逆序遍历体积，因为如果顺序遍历，dp[j - v[i]] 已经被更新过，而这里需要选取未被更新过的数据 */
        for (int j = V; j >= v[i]; --j) {
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }

    return dp[V];
}

/* 暴力动态规划，O(NV) */
int solve_0_1_backpack(vector<vector<int>> &goods, int V) {
    // 体积
    int v[goods.size() + 1];
    // 价值
    int w[goods.size() + 1];
    for (int i = 0; i < goods.size(); ++i) {
        v[i + 1] = goods[i][0];
        w[i + 1] = goods[i][1];
    }

    // 动态规划数组，dp[i][j] 表示前 i 个物品，体积 <= j 时的最大价值
    int dp[goods.size() + 1][V + 1];
    for (int i = 1; i <= goods.size(); ++i) {
        for (int j = 0; j <= V; ++j) {
            // 假设不选择第 i 个物品
            dp[i][j] = dp[i - 1][j];
            // 假设选择第 i 个物品，j 必须 >= v[i]
            if (j >= v[i]) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
            }
        }
    }

    return dp[goods.size()][V];
}

int main() {

}
